package breakthrough;
import java.util.ArrayList;
import java.util.Collections;
import game.*;

public class GLaDOSPlayer extends GamePlayer {
	public final int MAX_DEPTH = 50;
	public int depthLimit = 6;
	public static final double MAX_SCORE = Double.POSITIVE_INFINITY;
	//public static final double MIN_SCORE = Double.NEGATIVE_INFINITY; // REMOVE
	
	// mvStack is where the search procedure places it's move recommendation.
	// If the search is at depth, d, the move is stored on mvStack[d].
	// This was done to help efficiency (i.e., reduce number constructor calls)
	// (Not sure how much it improves things.)
	protected ScoredBreakthroughMove [] mvStack;
	
	 // A BreakthroughMove with a scored (how well it evaluates)
	protected class ScoredBreakthroughMove extends BreakthroughMove {
		public ScoredBreakthroughMove(int r1, int c1, int r2, int c2, double s)
		{
			super(r1,c1,r2,c2);
			score = s;
		}
		public void set(int r1, int c1, int r2, int c2, double s)
		{
			startRow = r1;
			startCol = c1;
			endingRow = r2;
			endingCol = c2;
			score = s;
		}
		public double score;
	}
	
	public GLaDOSPlayer(String n) {
		super(n, new BreakthroughState(), false);
	}
	
	public void messageFromOpponent(String m) {
		System.out.println(m);
	}
	
	/**
	 * Shuffle array
	 */
	/*private void shuffle(int [] ary)
	{
		int len = ary.length;
		for (int i=0; i<len; i++) {
			int spot = Util.randInt(i, len-1);
			int tmp = ary[i];
			ary[i] = ary[spot];
			ary[spot] = tmp;
		}
	}*/
	
	/**
	 * Initializes the stack of Moves.
	 */
	public void init()
	{
		mvStack = new ScoredBreakthroughMove [MAX_DEPTH];
		for (int i=0; i<MAX_DEPTH; i++) {
			mvStack[i] = new ScoredBreakthroughMove(0, 0, 0, 0, 0);
		}
	}
	
	/**
	 * Determines if a board represents a completed game. If it is, the
	 * evaluation values for these boards is recorded (i.e., 0 for a draw
	 * +X, for a HOME win and -X for an AWAY win.
	 * @param brd Breakthrough board to be examined
	 * @param mv where to place the score information; column is irrelevant
	 * @return true if the brd is a terminal state
	 */
	protected boolean terminalValue(GameState brd, ScoredBreakthroughMove mv)
	{
		GameState.Status status = brd.getStatus();
		boolean isTerminal = true;
		
		if (status == GameState.Status.HOME_WIN) {
			mv.set(0, 0, 0, 0, MAX_SCORE);
		} else if (status == GameState.Status.AWAY_WIN) {
			mv.set(0, 0, 0, 0, - MAX_SCORE);
		} else if (status == GameState.Status.DRAW) {
			mv.set(0, 0, 0, 0, 0);
		} else {
			isTerminal = false;
		}
		return isTerminal;
	}
	
	private ArrayList<BreakthroughMove> getMoveList(GameState state)
	{
		BreakthroughState board = (BreakthroughState)state;
		ArrayList<BreakthroughMove> list = new ArrayList<BreakthroughMove>();  
		BreakthroughMove mv = new BreakthroughMove();
		int dir = state.who == GameState.Who.HOME ? +1 : -1;
		for (int r=0; r<BreakthroughState.N; r++) {
			for (int c=0; c<BreakthroughState.N; c++) {
				mv.startRow = r;
				mv.startCol = c;
				mv.endingRow = r+dir; mv.endingCol = c;
				if (board.moveOK(mv)) {
					list.add((BreakthroughMove)mv.clone());
				}
				mv.endingRow = r+dir; mv.endingCol = c+1;
				if (board.moveOK(mv)) {
					list.add((BreakthroughMove)mv.clone());
				}
				mv.endingRow = r+dir; mv.endingCol = c-1;
				if (board.moveOK(mv)) {
					list.add((BreakthroughMove)mv.clone());
				}
			}
		}
		return list;
	}
	
	// NEEDS WORK
	/**
	 * Performs alpha beta pruning.
	 * @param brd
	 * @param currDepth
	 * @param alpha
	 * @param beta
	 */
	private void alphaBeta(BreakthroughState brd, int currDepth,
										double alpha, double beta)
	{
		boolean toMaximize = (brd.getWho() == GameState.Who.HOME);
		boolean toMinimize = !toMaximize;

		boolean isTerminal = terminalValue(brd, mvStack[currDepth]);
		
		if (isTerminal) {
			;
		} else if (currDepth == depthLimit) {
			mvStack[currDepth].set(0, 0, 0, 0, evalBoard(brd));
		} else {
			ScoredBreakthroughMove tempMv = new ScoredBreakthroughMove(0, 0, 0, 0, 0);

			double bestScore = (toMaximize ? 
					Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY);
			ScoredBreakthroughMove bestMove = mvStack[currDepth];
			ScoredBreakthroughMove nextMove = mvStack[currDepth+1];

			bestMove.set(0, 0, 0, 0, bestScore);
			//GameState.Who currTurn = brd.getWho();

			ArrayList<BreakthroughMove> moves = getMoveList(brd);

			//shuffle(columns);
			Collections.shuffle(moves);
						
			//for (int i=0; i<Connect4State.NUM_COLS; i++) {
			for (BreakthroughMove move : moves) {

				//int c = columns[i];
				//if (brd.numInCol[c] < Connect4State.NUM_ROWS) {
				//tempMv.col = c;				// initialize move
				//brd.makeMove(tempMv);
				tempMv.startRow = move.startRow;
				tempMv.startCol = move.startCol;
				tempMv.endingRow = move.endingRow;
				tempMv.endingCol = move.endingCol;
				
				BreakthroughState temp_brd = (BreakthroughState) brd.clone();
				temp_brd.makeMove(tempMv);

				alphaBeta(temp_brd, currDepth+1, alpha, beta);  // Check out move

				// Undo move
				//brd.numInCol[c]--;
				//int row = brd.numInCol[c]; 
				//brd.board[row][c] = Connect4State.emptySym;
				//brd.numMoves--;
				//brd.status = GameState.Status.GAME_ON;
				//brd.who = currTurn;

				// Check out the results, relative to what we've seen before
				if (toMaximize && nextMove.score > bestMove.score) {
					bestMove.set(move.startRow, move.startCol, move.endingRow, move.endingCol, nextMove.score);
				} else if (!toMaximize && nextMove.score < bestMove.score) {
					bestMove.set(move.startRow, move.startCol, move.endingRow, move.endingCol, nextMove.score);
				}

				// Update alpha and beta. Perform pruning, if possible.
				if (toMinimize) {
					beta = Math.min(bestMove.score, beta);
					if (bestMove.score <= alpha || bestMove.score == -MAX_SCORE) {
						return;
					}
				} else {
					alpha = Math.max(bestMove.score, alpha);
					if (bestMove.score >= beta || bestMove.score == MAX_SCORE) {
						return;
					}
				}
			}

		}
	}
	/**
	 * The evaluation function
	 * @param brd board to be evaluated
	 * @return Black evaluation - Red evaluation
	 */
	public static double evalBoard(BreakthroughState brd)
	{ 
		if (brd.status == GameState.Status.HOME_WIN) return Double.POSITIVE_INFINITY;
		else if (brd.status == GameState.Status.AWAY_WIN) return Double.NEGATIVE_INFINITY;
		
		int home = 0;
		int away = 0;
		for (int i = 0 ; i < BreakthroughState.N ; i++)
		{
			for (int j = 0 ; j < BreakthroughState.N ; j++)
			{
				if (brd.board[i][j] == BreakthroughState.homeSym) home++;
				if (brd.board[i][j] == BreakthroughState.awaySym) away++;
			}
		}
		return home - away;
	}
	
	/**
	 * invalid move = 0
	 * open move = 1
	 * attack move = 2
	 */
	private int possibleMove(BreakthroughState brd, int r, int c, int new_r, int new_c) {
		int move_state = 0;
		BreakthroughMove pm = new BreakthroughMove();
		pm.startCol = c;
		pm.startRow = r;
		pm.endingCol = new_c;
		pm.endingRow = new_r;
		if(brd.moveOK(pm) == true) {
			if(brd.board[new_r][new_c] == BreakthroughState.emptySym) {
				move_state = 1;
			}
			else {
				move_state = 2;
			}			
		}

		return move_state;
	}
	
	public GameMove getMove(GameState brd, String lastMove)
	{ 
		alphaBeta((BreakthroughState)brd, 0, Double.NEGATIVE_INFINITY, 
										 Double.POSITIVE_INFINITY);
		System.out.println(mvStack[0].score);
		return mvStack[0];
	}
	
	/*public GameMove getMove(GameState state, String lastMove) {
		BreakthroughState board = (BreakthroughState)state;
		BreakthroughMove mv = new BreakthroughMove();

		int i = 0;
		int j = 0;
		boolean noMoveFound = true;
		if(board.getWho().equals(GameState.Who.HOME)) {
			while(noMoveFound) {
				for(i = 0; i < BreakthroughState.N; i++) {
					for(j = 0; j < BreakthroughState.N; j++) {
						if(possibleMove(board, i, j, i+1, j) == 1) {
							mv.startRow = i;
							mv.startCol = j;
							mv.endingRow = i+1;
							mv.endingCol = j;
							noMoveFound = false;
						}
					}
				}
				System.out.println("LOOKING FOR MOVE (HOME) (" + i + "," + (j+1) + ")");
			}
		}
		else {
			while(noMoveFound) {
				for(i = 0; i < BreakthroughState.N; i++) {
					for(j = 0; j < BreakthroughState.N; j++) {
						if(possibleMove(board, i, j, i-1, j) == 1) {
							mv.startRow = i;
							mv.startCol = j;
							mv.endingRow = i-1;
							mv.endingCol = j;
							noMoveFound = false;
						}
					}
				}
				System.out.println("LOOKING FOR MOVE (AWAY) (" + (i-1) + "," + j + ")");
			}
		}
		
		return mv;
	}*/
	
	/*public GameMove getMove(GameState state, String lastMove) {
		
		BreakthroughState board = (BreakthroughState)state;
		ArrayList<BreakthroughMove> moves = new ArrayList<BreakthroughMove>();  
		ArrayList<BreakthroughMove> takes = new ArrayList<BreakthroughMove>();  
		BreakthroughMove mv = new BreakthroughMove();
		char opp = state.who == GameState.Who.HOME ?
				BreakthroughState.awaySym : BreakthroughState.homeSym;
		int dir = state.who == GameState.Who.HOME ? +1 : -1;
		for (int r=0; r<BreakthroughState.N; r++) {
			for (int c=0; c<BreakthroughState.N; c++) {
				mv.startRow = r;
				mv.startCol = c;
				mv.endingRow = r+dir; mv.endingCol = c;
				if (board.moveOK(mv)) {
					if (board.board[mv.endingRow][mv.endingCol] == opp) {
						takes.add((BreakthroughMove)mv.clone());
					} else {
						moves.add((BreakthroughMove)mv.clone());
					}
				}
				mv.endingRow = r+dir; mv.endingCol = c+1;
				if (board.moveOK(mv) && board.board[mv.endingRow][mv.endingCol] == opp) {
					if (board.board[mv.endingRow][mv.endingCol] == opp) {
						takes.add((BreakthroughMove)mv.clone());
					} else {
						moves.add((BreakthroughMove)mv.clone());
					}
				}
				mv.endingRow = r+dir; mv.endingCol = c-1;
				if (board.moveOK(mv) && board.board[mv.endingRow][mv.endingCol] == opp) {
					if (board.board[mv.endingRow][mv.endingCol] == opp) {
						takes.add((BreakthroughMove)mv.clone());
					} else {
						moves.add((BreakthroughMove)mv.clone());
					}
				}
			}
		}
		ArrayList<BreakthroughMove> list;  
		if (takes.size() > 0) {
			list = takes;
		} else {
			list = moves;
		}
		int which = Util.randInt(0, list.size()-1);
		return list.get(which);
	}*/
	
	public static void main(String [] args) {
		GamePlayer p = new GLaDOSPlayer("GLaDOS");
		p.compete(args);
	}
}
